We propose a novel piecewise stationary linear bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of an arm is measured by its return averaged over all contexts. The contexts and their distribution, as well as the changepoints are unknown to the agent.We design Piecewise-Stationary \varepsilon -Best Arm Identification (PS \varepsilon BAI), an algorithm that is guaranteed to identify an \varepsilon -optimal arm with probability \ge 1-\delta and with a minimal number of samples.PS \varepsilon BAI consists of two subroutines, PS \varepsilon BAI and Naïve \varepsilon -BAI (N \varepsilon BAI), which are executed in parallel. PS \varepsilon BAI actively detects changepoints and aligns contexts to facilitate the arm identification process.When PS \varepsilon BAI and N \varepsilon BAI are utilized judiciously in parallel, PS \varepsilon BAI is shown to have a finite expected sample complexity. By proving a lower bound, we show the expected sample complexity of PS \varepsilon BAI is optimal up to a logarithmic factor.We compare PS \varepsilon BAI to baseline algorithms using numerical experiments which demonstrate its efficiency.Both our analytical and numerical results corroborate that the efficacy of PS \varepsilon BAI is due to the delicate change detection and context alignment procedures embedded in PS \varepsilon BAI.

This study investigates a local asymptotic minimax optimal strategy for fixed-budget best arm identification (BAI). We propose the Adaptive Generalized Neyman Allocation (AGNA) strategy and show that its worst-case upper bound of the probability of misidentifying the best arm aligns with the worst-case lower bound under the small-gap regime, where the gap between the expected outcomes of the best and suboptimal arms is small. Our strategy corresponds to a generalization of the Neyman allocation for two-armed bandits (Neyman, 1934; Kaufmann et al., 2016) and a refinement of existing strategies such as the ones proposed by Glynn & Juneja (2004) and Shin et al. (2018). Compared to Komiyama et al. (2022), which proposes a minimax rate-optimal strategy, our proposed strategy has a tighter upper bound that exactly matches the lower bound, including the constant terms, by restricting the class of distributions to the class of small-gap distributions. Our result contributes to the longstanding open issue about the existence of asymptotically optimal strategies in fixed-budget BAI, by presenting the local asymptotic minimax optimal strategy.